// Package 二叉树序列化和反序列化 main
// @Title 二叉树序列化和反序列化  BFS实现
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-02-16 13:39
// @Create  2022-02-16 13:39
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main() {
	root := TreeNode{}
	//root.deserialize("1,2,3,4,5,6")
	fmt.Println(root.serialize(root.deserialize("1,2,3,4,5,6,X")))
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func (this *TreeNode) serialize(root *TreeNode) string {
	q := []*TreeNode{root}
	res := []string{}
	for len(q) != 0 {
		node := q[0]
		q = q[1:]
		if node != nil {
			res = append(res, strconv.Itoa(node.Val))
			q = append(q, node.Left)
			q = append(q, node.Right)
		} else {
			res = append(res, "NULL")
		}
	}
	return strings.Join(res, ",")
}

func (this *TreeNode) deserialize(data string) *TreeNode {
	if data == "X" {
		return nil
	}
	list := strings.Split(data, ",")
	Val, _ := strconv.Atoi(list[0])
	root := &TreeNode{Val: Val}
	q := []*TreeNode{root}
	cursor := 1
	for cursor < len(list) {
		node := q[0]
		q = q[1:]
		lV := list[cursor]
		rV := list[cursor+1]
		if lV != "X" {
			v, _ := strconv.Atoi(lV)
			lNode := &TreeNode{Val: v}
			node.Left = lNode
			q = append(q, lNode)
		}
		if rV != "X" {
			v, _ := strconv.Atoi(rV)
			rNode := &TreeNode{Val: v}
			node.Right = rNode
			q = append(q, rNode)
		}
		cursor += 2
	}
	return root
}
